//
// Created by wlly-lzh on 24-5-24.
//
#include "huffman.h"
/*
 * H的排序如下：
 * count: 8 8 7 6 5 4 3 2 1 0 0 0 0 0
 * ch   : a d r g s c e f a 0 0 0 0 0 (此处0 = null)
 * 注意：存在大量多余的树来充当连接结点
 * 8 8
 * 1 8
 *
 * */
// 查找最小的两棵树的索引，已知H为降序
// 其中 a为最小值的索引，b为次小值的索引
bool findmin(head * H,int * a,int * b){
	bool back=false;
	int x1=0,x2=0; // 索引
	int min1,min2; // 最小数 min1设定最小
	min1=min2=42000000; // 初始化为一个较大的值
	for(int i=0; i<SIZE_HEAD; ++i){
		if((*(H+i)).Parent == -1 && (*(H+i)).count > 0){
			// 没有父结点的树，且不属于多余的树
			if((*(H+i)).count < min1){ // 更新最小值
				min2=min1;
				min1=(*(H+i)).count;
				x2=x1;
				x1=i;
				back=true;
			}else if((*(H+i)).count < min2){
				min2=(*(H+i)).count;   // 更新第二小值
				x2=i;
				back=true;
			}
		}
	}
	*a=x1;
	*b=x2;
	return back;
}
// 查找空闲的多余结点的索引
void findfreeTree(head * H,int * num){
	for(int i=SIZE_HEAD-1; i>=0; --i){
		if((*(H+i)).count == 0){
			//if((*(H+i)).Left == -1 && (*(H+i)).Right== -1){
				// 没有权重，没有子树，肯定是多余的树
				// 貌似没有权重就是多余？ 以后再做讨论
				*num=i;
				return;
			//}
		}
	}
}
int create_huffman(head * H,int Size){
	int Length=Size; // head中树的数量
	int min1,min2;   // 最小
	int tmp;
	while(Length > 1){
		findmin(H,&min1,&min2);
		findfreeTree(H,&tmp);
		(*(H+min1)).Parent=tmp; // 最小树变子树
		(*(H+min2)).Parent=tmp;
		(*(H+tmp)).Left=min1;   // 中间树
		(*(H+tmp)).Right=min2;
		(*(H+tmp)).count=(*(H+min1)).count + (*(H+min2)).count; // 新权重
		Length--; // 每次都有两棵树合成一棵树
	}
	return tmp;
}

void Root(storage_tree * T,int * num){
	int i=0;
	while ((*(T+i)).Parent != -1){
		i=(*(T+i)).Parent;
	}
	*num=i;
}
// 遍历树，初始化索引
// ch - 路径符号，向左为 '0'，右为 '1'
// root - 索引;  level 递归的层次;
void Init_index(fast_index * I,head * H,char *path,char ch,int root,int level){
	if(level > 0) {
		path[level - 1]=ch;
	}
	if((*(H+root)).Left != -1){
		Init_index(I,H,path,'0',(*(H+root)).Left,level+1); // 左 - 0
	}
	if((*(H+root)).Right != -1){
		Init_index(I,H,path,'1',(*(H+root)).Right,level+1); // 右 - 1
	}
	unsigned char nowchar=(*(H+root)).ch;
	if((*(H+root)).Right == -1 && (*(H+root)).Left == -1){
		path[level]='\0';
		strcpy(I[(int)nowchar].code, path);
	}
}

void create_index(head * H,fast_index * I,int root){
	char path[128];
	Init_index(I,H,path,'/',root,0); // 此处的'/'无意义
}
bool find_element(storage_tree * tree,int * addr,char ch,unsigned char * find){
	// 待补充
	if(ch == '0'){
		*addr=tree[*addr].Left;
	}else if(ch == '1'){
		*addr=tree[*addr].Right;
	}
	if(tree[*addr].Right == -1 && tree[*addr].Left == -1){
		*find=tree[*addr].ch;
		return true;
	}
	return false;
}
